//
// Created by ASUS on 2024/10/12/星期六.
//
#include <bits/stdc++.h>
using namespace std;


class StringHash {
private:
	vector<int> pow_base1, pow_base2,pre_hash1, pre_hash2;
	int BASE1=13331;
	int BASE2=131;
	const int MOD1 = 1'070'777'777;
	const int MOD2 = 1'000'000'007;
public:
	//哈希主串
	StringHash(string&target) {
//		mt19937 gen{random_device{}()};
		mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
		BASE1 = uniform_int_distribution<>(8e8, 9e8)(rng); // 随机 base，防止 hack
		BASE2 = uniform_int_distribution<>(8e8, 9e8)(rng); // 随机 base，防止 hack

		int n = target.size();
		pow_base1.resize(n + 1); // pow_base[i] = base^i
		pow_base2.resize(n + 1); // pow_base[i] = base^i
		pre_hash1.resize(n + 1); // 前缀哈希值 pre_hash[i] = hash(s[:i])
		pre_hash2.resize(n + 1); // 前缀哈希值 pre_hash[i] = hash(s[:i])

		pow_base1[0] = 1;
		pow_base2[0] = 1;
		for (int i = 0; i < n; i++) {
			pow_base1[i + 1] = (long long) pow_base1[i] * BASE1 % MOD1;
			pow_base2[i + 1] = (long long) pow_base2[i] * BASE2 % MOD2;
			pre_hash1[i + 1] = ((long long) pre_hash1[i] * BASE1 + target[i]) % MOD1; // 秦九韶算法计算多项式哈希
			pre_hash2[i + 1] = ((long long) pre_hash2[i] * BASE2 + target[i]) % MOD2; // 秦九韶算法计算多项式哈希
		}
	}
	// 计算 target[l] 到 target[r-1] 的哈希值
	long long getHash(int l, int r) {
		long long  h1=((pre_hash1[r] - (long long) pre_hash1[l] * pow_base1[r - l]) % MOD1 + MOD1) % MOD1;
		long long  h2=((pre_hash2[r] - (long long) pre_hash2[l] * pow_base2[r - l]) % MOD2 + MOD2) % MOD2;
		return h1<<32|h2;
	}
	//哈希要匹配的子串
	long long getHash(string& t) {
		long long h1 = 0,h2=0;
		for (char& ch : t) {
			h1 = (h1 * BASE1 + ch) % MOD1;
			h2 = (h2 * BASE2 + ch) % MOD2;
		}
		return h1<<32|h2;
	}
};